Parallel distributed block coordinate descent methods based on pairwise comparison oracle

The aim of this paper is to find the global solutions of uncertain optimization problems having a quadratic objective function and quadratic inequality constraints. The bounded epistemic uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified ones. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for the proposed algorithm. The branch and bound algorithm presented in the paper handles both universally and existentially quantified parameters in a homogeneous way, without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding a robust, global solution. Several examples clarify the theoretical parts and the tests demonstrate the usefulness of the proposed method.     

Measuring centrality and dispersion in directional datasets: the ellipsoidal cone covering approach

Consider a finite collection \(\{\xi _k\}_{k=1}^p\) of vectors in the space \(\mathbb {R}^n\). The \(\xi _k\)’s are not to be seen as position points but as directions. This work addresses the problem of computing the ellipsoidal cone of minimal volume that contains all the \(\xi _k\)’s. The volume of an ellipsoidal cone is defined as the usual n-dimensional volume of a certain truncation of the cone. The central axis of the ellipsoidal cone of minimal volume serves to define the central direction of the datapoints, whereas its volume can be used as measure of dispersion of the datapoints.     

Accelerated parallel and distributed algorithm using limited internal memory for nonnegative matrix factorization

Nonnegative matrix factorization (NMF) is a powerful technique for dimension reduction, extracting latent factors and learning part-based representation. For large datasets, NMF performance depends on some major issues such as fast algorithms, fully parallel distributed feasibility and limited internal memory. This research designs a fast fully parallel and distributed algorithm using limited internal memory to reach high NMF performance for large datasets. Specially, we propose a flexible accelerated algorithm for NMF with all its \(L_1\) \(L_2\) regularized variants based on full decomposition, which is a combination of exact line search, greedy coordinate descent, and accelerated search. The proposed algorithm takes advantages of these algorithms to converges linearly at an over-bounded rate \((1-\frac{\mu }{L})(1 - \frac{\mu }{rL})^{2r}\) in optimizing each factor matrix when fixing the other factor one in the sub-space of passive variables, where r is the number of latent components, and \(\mu \) and L are bounded as \(\frac{1}{2} \le \mu \le L \le r\). In addition, the algorithm can exploit the data sparseness to run on large datasets with limited internal memory of machines, which is is advanced compared to fast block coordinate descent methods and accelerated methods. Our experimental results are highly competitive with seven state-of-the-art methods about three significant aspects of convergence, optimality and average of the iteration numbers.     

Chebyshev model arithmetic for factorable functions

This article presents an arithmetic for the computation of Chebyshev models for factorable functions and an analysis of their convergence properties. Similar to Taylor models, Chebyshev models consist of a pair of a multivariate polynomial approximating the factorable function and an interval remainder term bounding the actual gap with this polynomial approximant. Propagation rules and local convergence bounds are established for the addition, multiplication and composition operations with Chebyshev models. The global convergence of this arithmetic as the polynomial expansion order increases is also discussed. A generic implementation of Chebyshev model arithmetic is available in the library MC++. It is shown through several numerical case studies that Chebyshev models provide tighter bounds than their Taylor model counterparts, but this comes at the price of extra computational burden.     

Bounds tightening based on optimality conditions for nonconvex box-constrained optimization

First-order optimality conditions have been extensively studied for the development of algorithms for identifying locally optimal solutions. In this work, we propose two novel methods that directly exploit these conditions to expedite the solution of box-constrained global optimization problems. These methods carry out domain reduction by application of bounds tightening methods on optimality conditions. This scheme is implicit and avoids explicit generation of optimality conditions through symbolic differentation, which can be memory and time intensive. The proposed bounds tightening methods are implemented in the global solver BARON. Computational results on a test library of 327 problems demonstrate the value of our proposed approach in reducing the computational time and number of nodes required to solve these problems to global optimality.     

Vectorial penalization for generalized functional constrained problems

In this paper we use a double penalization procedure in order to reduce a set-valued optimization problem with functional constraints to an unconstrained one. The penalization results are given in several cases: for weak and strong solutions, in global and local settings, and considering two kinds of epigraphical mappings of the set-valued map that defines the constraints. Then necessary and sufficient conditions are obtained separately in terms of Bouligand derivatives of the objective and constraint mappings.     

On parallel Branch and Bound frameworks for Global Optimization

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.     

iGreen: green scheduling for peak demand minimization

Home owners are typically charged differently when they consume power at different periods within a day. Specifically, they are charged more during peak periods. Thus, in this paper, we explore how scheduling algorithms can be designed to minimize the peak energy consumption of a group of homes served by the same substation. We assume that a set of demand/response switches are deployed at a group of homes to control the activities of different appliances such as air conditioners or electric water heaters in these homes. Given a set of appliances, each appliance is associated with its instantaneous power consumption and duration, our objective is to decide when to activate different appliances in order to reduce the peak power consumption. This scheduling problem is shown to be NP-Hard. To tackle this problem, we propose a set of appliance scheduling algorithms under both offline and online settings. For the offline setting, we propose a constant ratio approximation algorithm (with approximation ratio \(\frac{1+\sqrt{5}}{2}+1\)). For the online setting, we adopt a greedy algorithm whose competitive ratio is also bounded. We conduct extensive simulations using real-life appliance energy consumption data trace to evaluate the performance of our algorithms. Extensive evaluations show that our schedulers significantly reduce the peak demand when compared with several existing heuristics.     

A switching for all strongly regular collinearity graphs from polar spaces

We describe a general construction of strongly regular graphs from the collinearity graph of a finite classical polar spaces of rank at least 3 over a finite field of order q. We show that these graphs are non-isomorphic to the collinearity graphs and have the same parameters. For most of these parameters, the collinearity graphs were the only known examples, and so many of our examples are new.     

On the additivity of block designs

We show that symmetric block designs \({\mathcal {D}}=({\mathcal {P}},{\mathcal {B}})\) can be embedded in a suitable commutative group \({\mathfrak {G}}_{\mathcal {D}}\) in such a way that the sum of the elements in each block is zero, whereas the only Steiner triple systems with this property are the point-line designs of \({\mathrm {PG}}(d,2)\) and \({\mathrm {AG}}(d,3)\). In both cases, the blocks can be characterized as the only k-subsets of \(\mathcal {P}\) whose elements sum to zero. It follows that the group of automorphisms of any such design \(\mathcal {D}\) is the group of automorphisms of \({\mathfrak {G}}_\mathcal {D}\) that leave \(\mathcal {P}\) invariant. In some special cases, the group \({\mathfrak {G}}_\mathcal {D}\) can be determined uniquely by the parameters of \(\mathcal {D}\). For instance, if \(\mathcal {D}\) is a 2-\((v,k,\lambda )\) symmetric design of prime order p not dividing k, then \({\mathfrak {G}}_\mathcal {D}\) is (essentially) isomorphic to \(({\mathbb {Z}}/p{\mathbb {Z}})^{\frac{v-1}{2}}\), and the embedding of the design in the group can be described explicitly. Moreover, in this case, the blocks of \(\mathcal {B}\) can be characterized also as the v intersections of \(\mathcal {P}\) with v suitable hyperplanes of \(({\mathbb {Z}}/p{\mathbb {Z}})^{\frac{v-1}{2}}\).